/*
题目: 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 */
public class InorderTraversal {
    List<Integer> list;
    public List<Integer> inorderTraversal(TreeNode root) {
        list = new ArrayList<> ();
        inorder(root);
        return list;
    }

    public void inorder(TreeNode root) {
        if (root == null) return ;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }
}


public class InorderTraversal {
    //子问题思想
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<> ();
        if (root == null) return list;
        list.addAll(inorderTraversal(root.left));
        list.add(root.val);
        list.addAll(inorderTraversal(root.right));
        return list;
    }
}

